package com.zhengb.algorithmdemo.basic.tree;

import com.zhengb.algorithmdemo.basic.queue.LinkListBaseQueue;
import com.zhengb.algorithmdemo.basic.stack.LinkListBaseStack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author zhengbo
 * @date 2020/2/20
 */
public class BinaryTreeUtils {

    /**
     * 递归方式查找二叉树最大的元素
     * 时间复杂度O(n) 空间复杂度O(n)
     *
     * @param rootNode
     * @return
     */
    public static int findMaxData(BinaryTreeNode<Integer> rootNode) {

        int rootVal, left, right, max = Integer.MIN_VALUE;

        if (rootNode != null) {
            rootVal = rootNode.getData();
            left = findMaxData(rootNode.getLeftNode());
            right = findMaxData(rootNode.getRightNode());

            if (left > right) {
                max = left;
            } else {
                max = right;
            }

            if (rootVal > max) {
                max = rootVal;
            }
        }

        return max;
    }

    /**
     * 利用层次遍历查找二叉树最大值
     * 时间复杂度O(n) 空间复杂度O(n)
     *
     * @param rootNode
     * @return
     */
    public static int findMaxUsingLevelOrder(BinaryTreeNode<Integer> rootNode) {

        BinaryTreeNode<Integer> tempNode;
        int max = Integer.MIN_VALUE;

        if (rootNode == null) {
            throw new IllegalArgumentException("");
        }

        LinkListBaseQueue<BinaryTreeNode<Integer>> queue = LinkListBaseQueue.createQueue();

        queue.enQueue(rootNode);

        while (!queue.isEmpty()) {

            tempNode = queue.deQueue();

            max = Integer.max(max, tempNode.getData());

            if (tempNode.getLeftNode() != null) {
                queue.enQueue(tempNode.getLeftNode());
            }
            if (tempNode.getRightNode() != null) {
                queue.enQueue(tempNode.getRightNode());
            }
        }
        return max;
    }

    /**
     * 递归方式查找二叉树值
     * 时间复杂度O(n) 空间复杂度O(n)
     *
     * @param rootNode
     * @param data
     * @param <T>
     * @return
     */
    public static <T> BinaryTreeNode<T> findElementInBinaryNode(BinaryTreeNode<T> rootNode, T data) {

        BinaryTreeNode<T> tempNode;

        if (rootNode == null || data == null) {
            return null;
        } else {
            if (data.equals(rootNode.getData())) {
                return rootNode;
            }
            tempNode = findElementInBinaryNode(rootNode.getLeftNode(), data);
            if (tempNode != null && tempNode.getData().equals(data)) {
                return tempNode;
            } else {
                return findElementInBinaryNode(rootNode.getRightNode(), data);
            }
        }
    }

    /**
     * 非递归方式查找二叉树值
     * 时间复杂度O(n) 空间复杂度O(n)
     *
     * @param rootNode
     * @param data
     * @param <T>
     * @return
     */
    public static <T> BinaryTreeNode<T> findElementInBinaryNodeUseLevelOrder(BinaryTreeNode<T> rootNode, T data) {

        BinaryTreeNode<T> tempNode;

        if (rootNode == null || data == null) {
            return null;
        }

        LinkListBaseQueue<BinaryTreeNode<T>> queue = LinkListBaseQueue.createQueue();

        queue.enQueue(rootNode);

        while (!queue.isEmpty()) {
            tempNode = queue.deQueue();

            if (tempNode.getData().equals(data)) {
                return tempNode;
            }
            if (tempNode.getLeftNode() != null) {
                queue.enQueue(tempNode.getLeftNode());
            }
            if (tempNode.getRightNode() != null) {
                queue.enQueue(tempNode.getRightNode());
            }
        }
        return null;
    }

    /**
     * 将一个元素插入到二叉树
     * 因为是二叉树 所有可以在任意地方插入
     * 利用队列遍历方法找到一个没有左孩子或右孩子的节点 然后插入该元素
     *
     * @param rootNode
     * @param data
     * @param <T>
     */
    public static <T> void insertInBinaryTreeNode(BinaryTreeNode<T> rootNode, T data) {

        LinkListBaseQueue<BinaryTreeNode<T>> queue = LinkListBaseQueue.createQueue();

        BinaryTreeNode<T> tempNode;

        BinaryTreeNode<T> newNode = new BinaryTreeNode<>();
        newNode.setRightNode(null);
        newNode.setLeftNode(null);
        newNode.setData(data);

        if (rootNode == null) {
            rootNode = newNode;
        }

        queue.enQueue(rootNode);

        while (!queue.isEmpty()) {
            tempNode = queue.deQueue();

            if (tempNode.getLeftNode() != null) {
                queue.enQueue(tempNode.getLeftNode());
            } else {
                tempNode.setLeftNode(newNode);
                queue.deleteQueue();
                return;
            }

            if (tempNode.getRightNode() != null) {
                queue.enQueue(tempNode.getRightNode());
            } else {
                tempNode.setRightNode(newNode);
                queue.deleteQueue();
                return;
            }
        }

    }

    /**
     * 递归求二叉树节点个数
     * 时间复杂度O(N) 空间复杂度O(N)
     *
     * @param rootNode
     * @param <T>
     * @return
     */
    public static <T> int sieOfBinaryTree(BinaryTreeNode<T> rootNode) {

        if (rootNode == null) {
            return 0;
        }
        return (sieOfBinaryTree(rootNode.getLeftNode()) + 1 + sieOfBinaryTree(rootNode.getRightNode()));
    }


    /**
     * 非递归求二叉树节点个数
     * 时间复杂度O(N) 空间复杂度O(N)
     *
     * @param rootNode
     * @param <T>
     * @return
     */
    public static <T> int sieOfBinaryTreeUsingLevelOrder(BinaryTreeNode<T> rootNode) {

        if (rootNode == null) {
            return 0;
        }

        LinkListBaseQueue<BinaryTreeNode<T>> queue = LinkListBaseQueue.createQueue();

        int size = 0;

        queue.enQueue(rootNode);

        BinaryTreeNode<T> tempNode;

        while (!queue.isEmpty()) {
            tempNode = queue.deQueue();
            size++;

            if (tempNode.getLeftNode() != null) {
                queue.enQueue(tempNode.getLeftNode());
            }

            if (tempNode.getRightNode() != null) {
                queue.enQueue(tempNode.getRightNode());
            }
        }

        queue.deleteQueue();

        return size;
    }

    /**
     * 递归方式删除树
     * 时间复杂度O(N) 空间复杂度O(N)
     *
     * @param rootNode
     * @param <T>
     */
    public static <T> void deleteBinaryTree(BinaryTreeNode<T> rootNode) {

        if (rootNode == null) {
            return;
        }

        deleteBinaryTree(rootNode.getLeftNode());
        deleteBinaryTree(rootNode.getRightNode());

        rootNode = null;
    }

    /**
     * 逆向逐层遍历树的元素
     * 时间复杂度O(N) 空间复杂度O(N)
     *
     * @param rootNode
     * @param <T>
     * @return
     */
    public static <T> List<T> levelOrderTraverseInReverse(BinaryTreeNode<T> rootNode) {

        if (rootNode == null) {
            return Collections.emptyList();
        }

        List<T> resultList = new ArrayList<>();

        LinkListBaseQueue<BinaryTreeNode<T>> queue = LinkListBaseQueue.createQueue();

        LinkListBaseStack<T> stack = new LinkListBaseStack<>();

        queue.enQueue(rootNode);

        BinaryTreeNode<T> tempNode;

        while (!queue.isEmpty()) {
            tempNode = queue.deQueue();

            stack.push(tempNode.getData());

            if (tempNode.getLeftNode() != null) {
                queue.enQueue(tempNode.getLeftNode());
            }

            if (tempNode.getRightNode() != null) {
                queue.enQueue(tempNode.getRightNode());
            }
        }

        while (!stack.isEmpty()) {
            resultList.add(stack.pop());
        }

        return resultList;
    }

    public static <T> int heightOfBinaryTree(BinaryTreeNode<T> rootNode) {

        int leftHeight, rightHeight;

        if (rootNode == null) {
            return 0;
        }

        leftHeight = heightOfBinaryTree(rootNode.getLeftNode());
        rightHeight = heightOfBinaryTree(rootNode.getRightNode());

        return Integer.max(leftHeight, rightHeight) + 1;
    }

    public static <T> int heightOfBinaryTreeNoRecursive(BinaryTreeNode<T> rootNode) {

        if (rootNode == null) {
            return 0;
        }

        int level = 0;

        LinkListBaseQueue<BinaryTreeNode<T>> queue = LinkListBaseQueue.createQueue();

        queue.enQueue(rootNode);
        //第一层结束
        queue.enQueue(null);

        BinaryTreeNode<T> tempNode;

        while (!queue.isEmpty()) {

            tempNode = queue.deQueue();

            if (tempNode == null) {
                if (!queue.isEmpty()) {
                    queue.enQueue(null);
                }
                level++;
            } else {
                if (tempNode.getLeftNode() != null) {
                    queue.enQueue(tempNode.getLeftNode());
                }
                if (tempNode.getRightNode() != null) {
                    queue.enQueue(tempNode.getRightNode());
                }
            }
        }
        return level;

    }


}
